package com.itdfq.LeetCode.leetcode.editor.cn;
//You are given a sorted integer array arr containing 1 and prime numbers,
//where all the integers of arr are unique. You are also given an integer k.
//
// For every i and j where 0 <= i < j < arr.length, we consider the fraction
//arr[i] / arr[j].
//
// Return the kᵗʰ smallest fraction considered. Return your answer as an array
//of integers of size 2, where answer[0] == arr[i] and answer[1] == arr[j].
//
//
// Example 1:
//
//
//Input: arr = [1,2,3,5], k = 3
//Output: [2,5]
//Explanation: The fractions to be considered in sorted order are:
//1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
//The third fraction is 2/5.
//
//
// Example 2:
//
//
//Input: arr = [1,7], k = 1
//Output: [1,7]
//
//
//
// Constraints:
//
//
// 2 <= arr.length <= 1000
// 1 <= arr[i] <= 3 * 10⁴
// arr[0] == 1
// arr[i] is a prime number for i > 0.
// All the numbers of arr are unique and sorted in strictly increasing order.
// 1 <= k <= arr.length * (arr.length - 1) / 2
//
// Related Topics Array Binary Search Heap (Priority Queue) 👍 662 👎 34


import java.util.PriorityQueue;

/**
 * @author GodChin
 * @date 2021-11-29 13:54:53
 * @title 第 K 个最小的素数分数
 * @blog https://itdfq.com
 */
class T786_KThSmallestPrimeFraction {
    public static void main(String[] args) {
        Solution solution = new T786_KThSmallestPrimeFraction().new Solution();
        int[] arr = new int[]{1, 2, 3, 5};
        int[] ints = solution.kthSmallestPrimeFraction(arr, 3);
        System.out.println(ints[0] + "-----" + ints[1]);

    }
    //leetcode submit region begin(Prohibit modification and deletion)

    class Solution {
        public int[] kthSmallestPrimeFraction(int[] arr, int k) {
            PriorityQueue<int[]> heap = new PriorityQueue<>((a, b)
                    -> arr[a[0]] * arr[b[1]] - arr[b[0]] * arr[a[1]]);
            for (int j = 1; j < arr.length; j++) {
                heap.offer(new int[]{0, j});
            }
            while (true) {
                int[] pos = heap.poll(); // 第k次弹出的就是结果
                if (--k <= 0) {
                    return new int[]{arr[pos[0]], arr[pos[1]]};
                }
                // 把弹出元素的后一个元素入队
                int i = pos[0];
                int j = pos[1];
                if (i + 1 < j) {
                    heap.offer(new int[]{i + 1, j});
                }
            }


            /** 暴力解决
             List<Tool> list = new ArrayList<>();
             for (int i = arr.length - 1; i > 0; i--) {
             for (int j = 0; j < i; j++) {
             list.add(new Tool((double) arr[j] / arr[i], arr[j], arr[i]));
             }
             }
             List<Tool> collect = list.stream().sorted(Comparator.comparing(Tool::getResult)).collect(Collectors.toList());
             int[] ints = new int[2];
             ints[0] = collect.get(k-1).getA();
             ints[1] = collect.get(k-1).getB();
             return ints;
             **/

        }
    }


//    class Tool {
//        private Double result;
//        private Integer a;
//        private Integer b;
//
//        public Double getResult() {
//            return result;
//        }
//
//        public Integer getA() {
//            return a;
//        }
//
//        public Integer getB() {
//            return b;
//        }
//
//        public Tool(Double result, Integer a, Integer b) {
//            this.result = result;
//            this.a = a;
//            this.b = b;
//        }
//    }
//leetcode submit region end(Prohibit modification and deletion)

}
